package com.example.leetcode.trainingcamp.week5.Sunday;

import java.util.HashSet;
import java.util.Set;

/**
 * 编写代码，移除未排序链表中的重复节点。保留最开始出现的节点。
 *
 * <p>示例1:
 *
 * <p>输入：[1, 2, 3, 3, 2, 1] 输出：[1, 2, 3] 示例2:
 *
 * <p>输入：[1, 1, 1, 1, 2] 输出：[1, 2]
 *
 * <p>来源：力扣（LeetCode） 链接：https://leetcode-cn.com/problems/remove-duplicate-node-lcci
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class Offer02_01 {

   // 1 1 1 1 2
    public ListNode removeDuplicateNodes(ListNode head) {
        Set<Integer> set = new HashSet<>();
        ListNode pre = head;
        ListNode newHead = new ListNode(-1);
        ListNode tail = newHead;
        while (pre != null){
            Integer val = pre.val;
            if (!set.contains(val)){
                tail.next = pre;
                tail = pre;
            }
            set.add(val);
            pre = pre.next;
        }
        tail.next = null;
        return newHead.next;
    }
}



class TestOffer02_01{
  public static void main(String[] args) {
    Offer02_01 o = new Offer02_01();
    ListNode head = new ListNode(1);
    head.next = new ListNode(1);
    head.next.next = new ListNode(1);
    head.next.next.next = new ListNode(1);
    head.next.next.next.next = new ListNode(2);
   // head.next.next.next.next.next = new ListNode(1);
    ListNode listNode = o.removeDuplicateNodes(head);
    while (listNode != null){
      System.out.print(listNode.val);
      listNode = listNode.next;
    }
  }
}